package gold.gold01;

import java.util.HashSet;
import java.util.Set;

/**
 * 简单
 * 对节点是否是相同节点(内存上, 不是值), 或者去重什么的, 就经常使用HashMap
 */
public class S0201移除重复节点 {
    /**
     * 89, set去重, 注意直接跳过第一个, 然后就是直接用add的返回值判断是否存在
     */
    public ListNode removeDuplicateNodes2(ListNode head) {
        if(head == null) return null;
        Set<Integer> recordSet = new HashSet<>();
        ListNode tempHead = head;
        recordSet.add(tempHead.val);
        while(tempHead.next != null){
            if(!recordSet.add(tempHead.next.val))
                tempHead.next = tempHead.next.next;
            else
                tempHead = tempHead.next;

        }
        return head;
    }
    /**
     * LeetCode抽风了, 什么玩意。
     * 因为val是int, 所以, 记录20000以内的数字是否存在, 需要20000位bitmap, 只要2.5kb。
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null) return null;
        ListNode pointer1 = head; // 先把头保留一下
        ListNode pointer2 = pointer1.next;
        int numTmp = pointer1.val;
        bitmap.putNum(numTmp);
        while(pointer2 != null){
            numTmp = pointer2.val;
            if(bitmap.isIn(numTmp)){
                pointer2 = pointer2.next;
                pointer1.next = pointer2;
            }else{
                bitmap.putNum(numTmp);
                pointer2 = pointer2.next;
                pointer1 = pointer1.next;
            }
        }


        return head;
    }
    // 这里有一个bitmap的实现, 绝了
    // 题目中有数字在0~20000之间, 这就有bitmap的感觉了
    private static class bitmap{
        private static final int[] bitmap = new int[20000/32 + 1];
        public static void putNum(int x){
            if(x > 20000) return;
            int loc = x >> 5; // 用右移代替 /32 是成熟的表现。
            int offset = x & 0x1F; // 用&0x1F 代替 %32 绝了。
            bitmap[loc] |= 1 << offset; // 绝了。取或代表给loc位置的int的offset位置1
        }
        public static boolean isIn(int x){
            if(x > 20000) return false;
            int loc = x >> 5;
            int offset = x & 0x1F;
            return (bitmap[loc] & 1 << offset) != 0; // 取&代表取出来那一位数, 绝了。
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(1);
        head.next.next.next.next = new ListNode(2);
        ListNode result = new S0201移除重复节点().removeDuplicateNodes(head);
        while (result != null){
            System.out.println(result.val);
            result = result.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}